package com.datastructures2.graph.最小生成树;

import com.datastructures2.tree2.BinaryHeap;
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.MinPQ;
import edu.princeton.cs.algs4.Queue;
import edu.princeton.cs.algs4.StdOut;

/**
 * 最小生成树Prim算法的延时实现
 * @author MaoLin Wang
 * @date 2020/2/2312:50
 */
public class LazyPrimMST {
    /**
     * 最小生成树的顶点
     */
    private boolean[] marked;

    /**
     * 最小生成树的边
     */
    private Queue<Edge> mst;

    /**
     * 横切边（包括失效的边）
     */
    private BinaryHeap<Edge> pq;

    public LazyPrimMST(EdgeWeightedGraph G){
        pq=new BinaryHeap<>();
        marked=new boolean[G.V()];
        mst=new Queue<>();

        //假设G是连通的
        visit(G,0);
        while (!pq.isEmpty()){
            //从pq中得到权重最小的边
            Edge edge = pq.deleteMin();
            int v=edge.either(),w=edge.other(v);
            if (marked[v]&&marked[w]){
                continue;
            }
            mst.enqueue(edge);
            if (!marked[v]){
                visit(G,v);
            }
            if (!marked[w]){
                visit(G,w);
            }
        }
    }

    /**
     * 将所有与v连接且未被标记的顶点的边加入横切边
     * @param G
     * @param v
     */
    private void visit(EdgeWeightedGraph G, int v) {
        marked[v]=true;
        for (Edge edge:G.adj(v)){
            if (!marked[edge.other(v)]){
                pq.insert(edge);
            }
        }
    }

    /**
     * 返回最小生成树的所有边
     * @return
     */
    public Iterable<Edge> edges(){
        return mst;
    }

    /**
     * 最小生成树的权重和
     * @return
     */
    public double weight(){
        double weight=0;
        for (Edge edge:mst){
            weight+=edge.weight();
        }
        return weight;
    }

    public static void main(String[] args) {
        In in = new In("D:\\JavaProject\\算法\\数据结构和算法\\DATAStructures\\alg\\src\\main\\java\\com\\datastructures2\\graph\\最小生成树\\tinyEWG.txt");
        EdgeWeightedGraph G = new EdgeWeightedGraph(in);
        LazyPrimMST mst = new LazyPrimMST(G);
        for (Edge e : mst.edges()) {
            StdOut.println(e);
        }
        StdOut.printf("%.5f\n", mst.weight());
    }
}
